﻿using System;
using System.Collections.Generic;

namespace DotNetCommon.Extensions
{
    using DotNetCommon;
    using DotNetCommon.Data;
    using System;
    using System.Collections.Concurrent;
    using System.Linq;
    using System.Linq.Expressions;
    using System.Reflection;

    /// <summary>
    /// <see cref="IEnumerable{T}"/>扩展类，树形结构操作
    /// </summary>
    public static class TreeExtensions
    {
        #region Remove
        /// <summary>
        /// 从集合中删除元素
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="collection"></param>
        /// <param name="predicate"></param>
        /// <returns>返回自身</returns>
        public static ICollection<T> Remove<T>(this ICollection<T> collection, Func<T, bool> predicate)
        {
            if (collection == null) return collection;
            collection.Where(predicate).ToList().ForEach(t => collection.Remove(t));
            return collection;
        }
        #endregion

        #region ToTree
        /// <summary>
        /// 根据指定的父节点和当前节点标记，从集合中提取为树状结构数据(原集合数据不改变)
        /// </summary>
        /// <typeparam name="T">集合中的数据模型</typeparam>
        /// <typeparam name="TId">数据模型中表示唯一标识类型</typeparam>
        /// <param name="collection"></param>
        /// <param name="idSelector">如何识别当前的节点</param>
        /// <param name="parentIdSelector">如何识别父节点</param>
        /// <param name="rootId">父节点默认的标识值</param>
        /// <returns>新构建的TreeNode集合</returns>
        public static TreeNode<T>[] ToTree<T, TId>(this IEnumerable<T> collection,
            Func<T, TId> idSelector,
            Func<T, TId> parentIdSelector,
            TId rootId = default)
                => collection.Where(x => EqualityComparer<TId>.Default.Equals(parentIdSelector(x), rootId))
                    .Select(x => new TreeNode<T>(x, collection.ToTree(idSelector, parentIdSelector, idSelector(x))))
                    .ToArray();

        /// <summary>
        /// 根据指定的父节点和当前节点标记，从集合中提取为树状结构数据
        /// </summary>
        /// <typeparam name="T">集合中的数据模型</typeparam>
        /// <typeparam name="TId">数据模型中表示唯一标识类型</typeparam>
        /// <param name="collection"></param>
        /// <param name="idSelector">如何识别当前的节点</param>
        /// <param name="parentIdSelector">如何识别父节点</param>
        /// <param name="isRoot">判断是否是根节点</param>
        public static TreeNode<T>[] ToTree<T, TId>(this IEnumerable<T> collection,
            Func<T, TId> idSelector,
            Func<T, TId> parentIdSelector,
            Func<T, bool> isRoot)
        {
            return collection.Where(x => isRoot(x))
                       .Select(x => new TreeNode<T>(x, collection.ToTree(idSelector, parentIdSelector, t => EqualityComparer<TId>.Default.Equals(parentIdSelector(t), idSelector(x))).ToArray())).ToArray();
        }
        #endregion

        #region FetchToTree 
        /// <summary>
        /// 从扁平的集合数据中提取树状结构（原集合数据不变）
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <typeparam name="TId"></typeparam>
        /// <param name="collection"></param>
        /// <param name="idSelector">Id选择器,如: t=>t.Id</param>
        /// <param name="parentIdSelector">PId选择器,如: t=>t.PId</param>
        /// <param name="childrenSelectorExpression">子节点集合选择表达式，如: t=>t.Children</param>
        /// <param name="isRoot">用来判断是否是根节点(默认为null,即:使用TId的默认值)</param>
        /// <returns>提取出来的树状结构数据</returns>
        public static List<T> FetchToTree<T, TId>(this IEnumerable<T> collection,
           Func<T, TId> idSelector,
           Func<T, TId> parentIdSelector,
           Expression<Func<T, IEnumerable<T>>> childrenSelectorExpression,
           Func<T, bool> isRoot = null)
        {
            if (childrenSelectorExpression.Body is not MemberExpression) throw new Exception($"参数{nameof(childrenSelectorExpression)}必须是一个MemberExpression，如: t=>t.Children");
            var member = childrenSelectorExpression.Body as MemberExpression;
            var prop = typeof(T).GetProperty(member.Member.Name);
            return _fetchToTree(collection, idSelector, parentIdSelector, isRoot, prop).ToList();
        }

        /// <summary>
        /// 将扁平的集合数据转为树状结构（原集合数据不变）
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <typeparam name="TId"></typeparam>
        /// <param name="collection"></param>
        /// <param name="idSelector">Id选择器,如: t=>t.Id</param>
        /// <param name="parentIdSelector">PId选择器,如: t=>t.PId</param>
        /// <param name="isRoot">用来判断是否是根节点(默认为null,即:使用TId的默认值)</param>
        /// <returns>提取出来的树状结构数据</returns>
        public static List<T> FetchToTree<T, TId>(this IEnumerable<T> collection,
           Func<T, TId> idSelector,
           Func<T, TId> parentIdSelector,
           Func<T, bool> isRoot = null) where T : ITreeStruct<T>
        {
            var prop = typeof(ITreeStruct<T>).GetProperty("Children");
            return _fetchToTree(collection, idSelector, parentIdSelector, isRoot, prop).ToList();
        }

        private static ICollection<T> _fetchToTree<T, TId>(this IEnumerable<T> collection,
           Func<T, TId> idSelector,
           Func<T, TId> parentIdSelector,
           Func<T, bool> isRoot,
           PropertyInfo prop)
        {
            if (isRoot == null)
            {
                isRoot = t => EqualityComparer<TId>.Default.Equals(parentIdSelector(t), default(TId));
            }
            var roots = collection.Where(isRoot).ToList();
            collection = collection.Except(roots).ToList();
            FetchChildren(roots, collection, idSelector, parentIdSelector);
            return roots;
            void FetchChildren(List<T> parents, IEnumerable<T> collection,
                Func<T, TId> idSelector,
                Func<T, TId> parentIdSelector)
            {
                //先找根节点
                parents.ForEach(r =>
                {
                    var children = collection.Where(c => EqualityComparer<TId>.Default.Equals(parentIdSelector(c), idSelector(r))).ToList<T>();
                    prop.SetValue(r, children);
                    collection = collection.Except(children).ToList();
                    FetchChildren(children, collection, idSelector, parentIdSelector);
                });
            }
        }
        #endregion

        #region ToFlat
        /// <summary>
        /// 将任意多级的树形列表展开(返回新的平铺集合，当treeToFlatAction参数为SetEmpty时原集合的Children属性被重置)
        /// </summary>
        /// <param name="srcArr">原属树形表</param>
        /// <param name="childrenSelectorExpression">获取子节点集合</param>
        /// <param name="treeToFlatAction">转为平铺数据后,针对原集合元素的Children属性的设置,默认为none,即:不设置</param>
        /// <returns></returns>
        public static List<T> ToFlat<T>(this IEnumerable<T> srcArr, Expression<Func<T, IEnumerable<T>>> childrenSelectorExpression, TreeToFlatAction treeToFlatAction = TreeToFlatAction.None)
        {
            if (childrenSelectorExpression.Body is not MemberExpression) throw new Exception($"参数{nameof(childrenSelectorExpression)}必须是一个MemberExpression，如: t=>t.Children");
            var member = childrenSelectorExpression.Body as MemberExpression;
            var prop = typeof(T).GetProperty(member.Member.Name);
            var getChildren = childrenSelectorExpression.Compile();

            var res = _ToFlat(srcArr);
            if (treeToFlatAction == TreeToFlatAction.SetEmpty)
            {
                res.ForEach(i =>
                {
                    var children = getChildren(i);
                    //如果为null则不作更改
                    if (children == null) return;
                    //如果为ICollection,直接清空
                    if (children is ICollection<T> collection)
                    {
                        collection.Clear();
                    }
                    else if (prop.CanWrite && children is IEnumerable<T>)
                    {
                        prop.SetValue(i, new T[0]);
                    }
                });
            }
            else if (treeToFlatAction == TreeToFlatAction.SetNull)
            {
                if (prop.CanWrite)
                {
                    res.ForEach(i =>
                    {
                        if (getChildren(i) != null)
                        {
                            prop.SetValue(i, null);
                        }
                    });
                }
            }
            else if (treeToFlatAction == TreeToFlatAction.SetEmptyCollection)
            {
                if (prop.CanWrite)
                {
                    res.ForEach(i =>
                    {
                        var children = getChildren(i);
                        if (children == null)
                        {
                            prop.SetValue(i, new List<T>());
                        }
                        else
                        {
                            //如果为ICollection,直接清空
                            if (children is ICollection<T> collection)
                            {
                                collection.Clear();
                            }
                            else if (prop.CanWrite && children is IEnumerable<T>)
                            {
                                //如果为数组或IEnumerable则设为空数组
                                prop.SetValue(i, new T[0]);
                            }
                        }
                    });
                }
            }
            return res;

            List<T> _ToFlat(IEnumerable<T> srcArr)
            {
                var res = new List<T>();
                if (srcArr != null && srcArr.Count() > 0)
                {
                    srcArr.ForEach(i =>
                    {
                        res.Add(i);
                        var children = getChildren(i);
                        if (children != null && children.Count() > 0)
                        {
                            var list = _ToFlat(children);
                            if (list != null && list.Count > 0) res.AddRange(list);
                        }
                    });
                }
                return res;
            }
        }
        #endregion

        #region FilterTree
        /// <summary>
        /// 过滤树结构(注意原始集合已改变)
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="tree"></param>
        /// <param name="childrenSelector"></param>
        /// <param name="filterExpression">单个节点的过滤条件</param>
        /// <param name="withAllChildren">当单个节点通过后是否直接连带子节点到输出结果树中</param>
        /// <param name="tmpList">临时存放分支上首个命中节点</param>
        /// <remarks>过滤的过程是在原树形集合上做减法</remarks>
        /// <returns>返回自身</returns>
        private static void FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Predicate<T> filterExpression, bool withAllChildren, List<T> tmpList)
        {
            //倒序遍历,方便移除
            for (var i = tree.Count - 1; i >= 0; i--)
            {
                var child = tree[i];
                var showme = false;
                if (filterExpression(child))
                {
                    showme = true;
                    if (tmpList != null) tmpList.Add(child);
                }
                //当前节点已命中且指定返回所有子节点,可以直接返回了
                if (withAllChildren && showme) continue;
                var showchild = false;
                var children = childrenSelector(child);
                if (children != null && children.Count > 0)
                {
                    FilterTree(children, childrenSelector, filterExpression, withAllChildren, showme ? null : tmpList);
                    if (children.Count > 0)
                    {
                        showchild = true;
                    }
                }
                if (showme == false && showchild == false)
                {
                    //自身和字节点均没有被命中，则移除自身
                    tree.RemoveAt(i);
                }
            }
        }

        /// <summary>
        /// 过滤树结构(注意原始集合已改变)
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="tree"></param>
        /// <param name="childrenSelector"></param>
        /// <param name="filterExpression">单个节点的过滤条件</param>
        /// <param name="withAllChildren">当单个节点通过后是否直接连带子节点到输出结果树中</param>
        /// <param name="withAllParents">当单个节点通过后是否输出当前节点的所有父节点到结果树中</param>
        /// <remarks>过滤的过程是在原树形集合上做减法</remarks>
        /// <returns>返回自身</returns>
        public static List<T> FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Predicate<T> filterExpression, bool withAllChildren = false, bool withAllParents = true)
        {
            List<T> tmpList = null;
            if (!withAllParents)
            {
                //不输出父节点,则收集分支上首个命中的节点
                tmpList = new List<T>();
            }
            FilterTree(tree, childrenSelector, filterExpression, withAllChildren, tmpList);
            if (withAllParents) return tree.ToList();
            else
            {
                tree.Clear();
                tree.AddRange(tmpList);
                return tree.ToList();
            }
        }
        #endregion

        #region RecurseTree
        /// <summary>
        /// 递归树结构
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="tree"></param>
        /// <param name="childrenSelector"></param>
        /// <param name="action">节点处理逻辑(node:当前节点,isLeaf:是否是叶子节点,deepIndex:深度索引,parents:父节点集合)</param>
        /// <returns>返回自身</returns>
        public static List<T> RecurseTree<T>(this ICollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<RecurseTreeContext<T>> action)
        {
            var list = tree.ToList();
            foreach (var node in list)
            {
                var children = childrenSelector(node);
                var isLeaf = children == null || children.Count() == 0;
                var ctx = new RecurseTreeContext<T>()
                {
                    Current = node,
                    IsLeaf = isLeaf,
                    Parent = null
                };
                _recurseTree(ctx);
                if (ctx.BreakRquested) break;
            }
            return list;

            void _recurseTree(RecurseTreeContext<T> ctx)
            {
                action(ctx);
                //中断遍历
                if (ctx.BreakRquested)
                {
                    if (ctx.Parent != null) ctx.Parent.BreakRquested = true;
                    return;
                }
                //继续下个兄弟节点遍历
                if (ctx.NextSiblingRquested) return;
                if (!ctx.IsLeaf)
                {
                    //遍历子节点
                    //先把自身加入上下文
                    ctx.Parents.Add(ctx.Current);
                    var children = childrenSelector(ctx.Current);
                    foreach (var n in children)
                    {
                        //深度+1
                        ctx.InternalConter.Deep++;
                        var childrenNew = childrenSelector(n);
                        var isLeafNew = childrenNew == null || childrenNew.Count() == 0;
                        var newCtx = new RecurseTreeContext<T>
                        {
                            Current = n,
                            IsLeaf = isLeafNew,
                            Parent = ctx
                        };
                        //递归调用
                        _recurseTree(newCtx);
                        //深度-1
                        ctx.InternalConter.Deep--;
                        if (newCtx.BreakRquested)
                        {
                            if (newCtx.Parent != null) newCtx.Parent.BreakRquested = true;
                            return;
                        }
                    }
                    //把自身从上下文中移除
                    var index = ctx.Parents.LastIndexOf(ctx.Current);
                    ctx.Parents.RemoveAt(index);
                }
            }
        }
        #endregion
    }

    /// <summary>
    /// ICollection.ToFlat()方法的参数
    /// </summary>
    public enum TreeToFlatAction
    {
        /// <summary>
        /// 不对原有的Children属性做任何操作
        /// </summary>
        None,
        /// <summary>
        /// 设置为空集合(原来的Children为null则为null，否则为空集合)
        /// </summary>
        SetEmpty,
        /// <summary>
        /// 设置为空集合(将原来的Children设为null)
        /// </summary>
        SetNull,
        /// <summary>
        /// 设置为空集合(将原来的Children设为元素个数为空的集合)
        /// </summary>
        SetEmptyCollection
    }

    /// <summary>
    /// 树节点遍历上下文
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class RecurseTreeContext<T>
    {
        /// <summary>
        /// 当前节点
        /// </summary>
        public T Current { get; internal set; }
        /// <summary>
        /// 当前节点深度,从0开始
        /// </summary>
        public int DeepIndex => InternalConter.Deep;
        /// <summary>
        /// 当前节点是否是叶子节点
        /// </summary>
        public bool IsLeaf { get; internal set; }

        private List<T> _parents = null;
        /// <summary>
        /// 当前节点的父节点集合
        /// </summary>
        /// <remarks>注意: 一条线共用一个集合，所以不要在这里增减上面的内容, 可以使用 ctx.Parents.ToList() 产生新的集合</remarks>
        public List<T> Parents
        {
            get
            {
                if (_parents == null)
                {
                    // _parents: 其实这个属性只有在根节点才有值
                    if (Parent == null || Parent.Parents == null) _parents = new List<T>();
                    else _parents = Parent.Parents;
                }
                return _parents;
            }
        }

        /// <summary>
        /// 当前节点的父节点集合(包含自身)
        /// </summary>
        public List<T> ParentsWithSelf
        {
            get
            {
                var arr = new T[Parents.Count];
                Parents.CopyTo(arr);
                var list = arr.ToList();
                list.Add(Current);
                return list;
            }
        }

        /// <summary>
        /// 中断遍历
        /// </summary>
        public void BreakRecurse()
        {
            BreakRquested = true;
        }

        /// <summary>
        /// 继续下个兄弟节点的遍历
        /// </summary>
        public void NextSibling()
        {
            NextSiblingRquested = true;
        }

        /// <summary>
        /// 是否请求中断遍历
        /// </summary>
        internal bool BreakRquested { set; get; }

        /// <summary>
        /// 是否请求继续下个兄弟节点遍历
        /// </summary>
        internal bool NextSiblingRquested { set; get; }

        /// <summary>
        /// 父节点
        /// </summary>
        internal RecurseTreeContext<T> Parent { get; set; }

        private Counter _counter = null;
        /// <summary>
        /// 深度(仅存储在根节点)
        /// </summary>
        internal Counter InternalConter
        {
            get
            {
                if (_counter == null)
                {
                    if (Parent == null || Parent.InternalConter == null) _counter = new Counter();
                    else _counter = Parent.InternalConter;
                }
                return _counter;
            }
        }
    }

    internal class Counter
    {
        public int Deep { get; set; }
    }

}